//
// Description: 归并排序 模板
// Created by Loading on 2021/10/10.
//

#include <bits/stdc++.h>

using namespace std;

void merge_sort(vector<int> &nums, int l, int r) {
    if (l >= r) {
        return;
    }

    // 取中点
    int mid = l + (r - l) / 2;

    // 左右两侧分别递归归并
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);

    int index = 0;
    int i = l, j = mid + 1;
    // 临时数组，存放归并排序后的结果
    vector<int> tmp(r - l + 1);
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) {
            tmp[index++] = nums[i++];
        } else {
            tmp[index++] = nums[j++];
        }
    }

    // 将剩余数据追加
    while (i <= mid) {
        tmp[index++] = nums[i++];
    }
    while (j <= r) {
        tmp[index++] = nums[j++];
    }

    // 归并排序结果写回原数组
    for (i = l, j = 0; i <= r; ++i, ++j) {
        nums[i] = tmp[j];
    }
}

int main() {
    vector<int> nums = {4, 1, 7, 6, 9, 2, 8, 0, 3, 5};
    merge_sort(nums, 0, (int) nums.size() - 1);
    for (auto &x : nums) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}